package com.fr.lintcode;

public class Q1538 {
	/**
	 * @param cost:        costs of all cards
	 * @param damage:      damage of all cards
	 * @param totalMoney:  total of money
	 * @param totalDamage: the damage you need to inflict
	 * @return: Determine if you can win the game
	 */
	public boolean cardGame(int[] cost, int[] damage, int totalMoney, int totalDamage) {
		// Write your code here
		if (cost == null) {
			return false;
		}
		int[][] dp = new int[cost.length][totalMoney + 1];
		for (int j = 0; j <= totalMoney; j++) {
			dp[0][j] = (j >= cost[0] ? damage[0] : 0);
		}
		
 
        for (int i = 1; i < cost.length; i++) {
            for (int j = 0; j <= totalMoney; j++) {
            	dp[i][j] = dp[i - 1][j];
                if (j >= cost[i])
                	dp[i][j] = Math.max(dp[i][j], damage[i] + dp[i - 1][j - cost[i]]);
            }
        }
        return dp[cost.length - 1][totalMoney] >= totalDamage;
	}
}
